#include <stdio.h>
#include <omp.h>
#include <stdlib.h>

#define BLOCK_LOW(id,p,n) (((id)*(n))/(p))
#define BLOCK_HIGH(id,p,n) (BLOCK_LOW((id)+1,(p),(n)) - 1)



void find_prime(int v[], int low, int high, int prime, int MAXNUM) {

    int j = 0;
    int k = 0;

    /*for ( j = low; (j%prime) != 0 && j < high && j < MAXNUM; j++ );
    
    
    if ( (j%prime) == 0 ) {
    	v[j] = 0;
   	    for ( j; j <= high && j < MAXNUM; j += prime ) {
	 	     v[j] = 0;
    	}
    }
    */
    //Nova Proposta do codigo
    j = (low-1)/prime;
    j = (j+1)*prime;
   	for ( j; j <= high && j < MAXNUM; j += prime ) {
	     v[j] = 0;
    }
}

int next_prime(int v[], int ini, int MAXNUM) {

    int i = ini;
    while (v[i] == 0 && i < MAXNUM)
        i++;

    return i;

}

void print_prime(int v[], int MAXNUM) {

	int i = 0;
	for ( i = 0; i < MAXNUM; i++ )
	    if ( v[i] ) printf("%d\n",i);

}

int crivo(int np, int x) {

    int global_sum = 0;
    int i = 0;
    int MAXNUM = x+1;
    int v[MAXNUM];
    int low;
    int high;
    int p;

    for ( i = 0; i < MAXNUM; i++ )
        v[i] = 1;

    v[0] = 0;
    omp_set_num_threads(np);

    #pragma omp parallel shared(v) private(p,low,high)
    {
        p = 2;
        while (p*p <= MAXNUM) {

            low = BLOCK_LOW(omp_get_thread_num(),np,MAXNUM-p*p)+(p*p);
            high = BLOCK_HIGH(omp_get_thread_num(),np,MAXNUM-p*p)+(p*p);
            find_prime(v,low,high,p, MAXNUM);
            p = next_prime(v,p+1, MAXNUM);

        }
    }

    if (v[MAXNUM-1] == 1)
            return 1;
    else
            return 0;

}
